#include<iostream>
#include<stack>
using namespace std;


int map02[9][9] = {
	{0, 0, 5,  3, 0, 0,  0, 0, 0},
	{8, 0, 0,  0, 0, 0,  0, 2, 0},
	{0, 7, 0,  0, 1, 0,  5, 0, 0},

	{4, 0, 0,  0, 0, 5,  3, 0, 0},
	{0, 1, 0,  0, 7, 0,  0, 0, 6},
	{0, 0, 3,  2, 0, 0,  0, 8, 0},

	{0, 6, 0,  5, 0, 0,  0, 0, 9},
	{0, 0, 4,  0, 0, 0,  0, 3, 0},
	{0, 0, 0,  0, 0, 9,  7, 0, 0}
};//初始化

//检查每一个九宫格时，每次都定位在(x, y)所在的 九宫格的中心 ，然后才开始向周围遍历
int x02[9] = { -1, -1, -1, 0,  0, 0,  1, 1, 1 };
int y02[9] = { -1,  0,  1, -1, 0, 1, -1, 0, 1 };

stack<int> stk02;//保存的是做出修改的空格的下标（1~81）
//只有当后面的格子中出现了无论如何都不能实现的情况，才会回溯回来

void print_shudu()
{
	cout << "数独的解为：" << endl;
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cout << map02[i][j] << " ";
			if ((j + 1) % 3 == 0) cout << " ";
		}
		cout << endl;
		if ((i + 1) % 3 == 0) cout << endl;
	}
}

bool check02(int x, int y, int num)//查询 (x, y) 填入数字 num 是否可行
{
	//检查行、列
	for (int i = 0; i < 9; i++)
	{
		if (map02[i][y] == num) //第 y 列有数字 num
			return false;//填入数字 num 不可行
		if (map02[x][i] == num) //第 x 行有数字 num
			return false;
	}

	//检查(x, y)所在的九宫格
	int center_x = x / 3 * 3 + 1;//寻找中心
	int center_y = y / 3 * 3 + 1;
	for (int i = 0; i < 9; i++)
	{
		int tmpx = center_x + x02[i];
		int tmpy = center_y + y02[i];

		if (map02[tmpx][tmpy] == num) return false;
		else continue;
	}

	return true;//都检查完了还是没有因为错误返回
}

int find_space()//查找下一个可填入的位置, 从loc开始查找
{
	for (int i = 0; i < 81; i++)
	{
		int x = i / 9;
		int y = i % 9;

		if (map02[x][y] == 0)
			return i;
	}

	return -1;//也可能没有找到空格，这象征着数独问题解的结束
}

bool shudu()
{
	stk02.push(find_space());//寻找空格

	int num;
	while (stk02.top() >= 0)
	{
		int loc = stk02.top();//查看空格
		int x = loc / 9;
		int y = loc % 9;

		num = map02[x][y] + 1;
		while (num <= 9 && check02(x, y, num) == false)num ++ ;

		if (num > 9)
		{
			stk02.pop();//无法匹配，弹出空格，说明上面的步骤出了问题
			map02[x][y] = 0;//重置
		}
		else
		{
			map02[x][y] = num;
			stk02.push(find_space());//继续寻找下一个空格
		}

	}

	if (stk02.empty() == true)//如果栈为空，说明已经把所有情况都试过了，回退到了最开始的位置
	{
		return false;
	}
	else
	{
		return true;
	}

}

int main(){ 
    bool res02 = shudu();
	if (res02 == true)
	{
		print_shudu();
	}
	else
	{
		cout << "该数独问题无解!!!" << endl;
	}
}
